package com.zhu.solution.writtenExamination;

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;

/**
 * Created with IntelliJ IDEA.
 *
 * @Author: zhujiabao
 * @Date: 2023/10/24/21:57
 * @Description: 先集合的交集，再求并集
 *
 * 输入
 * 0 3
 * 1 3
 * 3 5
 * 3 6
 * exit
 * 输出
 * 1 5
 *
 *
输入
0 3
1 3
4 5
4 6
exit
输出
1 3
4 5
 */
public class IntersectionoOfSets {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 创建一个优先队列，按照区间的起始位置进行排序
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        while (in.hasNextInt()) {
            int start = in.nextInt();
            int end = in.nextInt();
            // 将区间添加到优先队列中
            pq.offer(new int[]{start, end});
        }
        List<int[]> res = new ArrayList<>();
        // 从优先队列中取出一个区间
        int[] curInterval = pq.poll();
        while (!pq.isEmpty()) {
            // 如果当前区间和优先队列中的下一个区间有交集，合并这两个区间
            if (curInterval[1] >= pq.peek()[0]) {

                curInterval[0] = Math.max(curInterval[0], pq.peek()[0]);
                curInterval[1] = Math.min(curInterval[1], pq.peek()[1]);
                System.out.println(curInterval[0] + " , " + curInterval[1]);
                res.add(curInterval);
                curInterval = pq.poll();
            } else {
                // 如果当前区间和优先队列中的下一个区间没有交集，将当前区间添加到结果列表中，并更新当前区间
                curInterval = pq.poll();
            }
        }
        // 将最后一个区间添加到结果列表中
//        res.add(curInterval);
        for (int[] interval : res) {
            System.out.println(interval[0] + " " + interval[1]);
        }

        System.out.println("-------------------");

        method(res);




    }

    private static void method(List<int[]> res){
        List<int[]> resNew = new ArrayList<>();
        //再取并集
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        // 将区间添加到优先队列中
        for (int[] interval : res) {
            pq.offer(interval);
        }
        int[] curInterval = pq.poll();
        while (!pq.isEmpty()) {
            // 如果当前区间和优先队列中的下一个区间有交集，合并这两个区间
            if (curInterval[1] >= pq.peek()[0]) {
                curInterval[1] = Math.max(curInterval[1], pq.peek()[1]);
//                System.out.println(curInterval[0] + " , " + curInterval[1]);
                pq.poll();
            } else {
                // 如果当前区间和优先队列中的下一个区间没有交集，将当前区间添加到结果列表中，并更新当前区间
                resNew.add(curInterval);
                curInterval = pq.poll();
            }
        }
        // 将最后一个区间添加到结果列表中
        resNew.add(curInterval);
        for (int[] interval : resNew) {
            System.out.println(interval[0] + " " + interval[1]);
        }
    }
}
